1. Field of the Invention
This invention relates to computer circuits and, more particularly, to methods and apparatus for rapidly generating the carry out signals for adder circuits.
2. History of the Prior Art
Adder circuits are used in digital computers for many purposes. In most of those uses, the speed of those circuits is paramount. For example, the primary manner in which the sequential flow of information is changed in a digital computer is through the use of conditional branch operations. In general, a conditional branch operation depends on some arithmetic operation and, based on the result, makes a decision whether or not to branch to a particular address. The result of the arithmetic operation usually involves a summation, carry outs, and a sign; and the decision may depends on any of these elements, combinations of these elements, or flags generated from these elements. The length of time required to generate flags which depend on the final carry out value is usually the critical element and is, consequently, a major factor in achieving higher processor speed.
There has been a plethora of work directed to improving the speed of adders. Much of this work has been directed to improving the speed of computation of the carry out since this computation usually takes the longest time. This is true because the carry out from the most significant stage depends on what has happened at each of the lower stages of the addition. Typically, the carry out at each stage is computed along with the computation of the sum. Ultimately, the carry out and the sum are used to compute other factors necessary for deciding the conditional branch functions.
Carry look ahead, carry select, and Manchester carry chain schemes are some of the fast hardware implementations of adders. Carry look ahead adders and Manchester carry chain adders are limited in speed because their operation is inherently serial in nature. Carry select adders, on the other hand, compute two results of groups of digits in parallel and select the correct one of the two after the carry-in value to the group is known. When a number of columns are computed in parallel as subsets, at least in theory very fast operation could result. However, in reality such adders take up a great deal of circuitry and are therefore expensive to implement and slower than theoretically predicted. An arrangement is needed which operates rapidly yet does not utilize the very large amount of circuitry required by the prior art.
One form of adder which in theory produces very fast results is the conditional sum adder described by J. Sklansky in an article entitled "Conditional-Sum Addition Logic", published in June 1960, IRE Transactions On Electronic Computers. Although it was suggested that this form of adder would produce very fast results, the very large number of gates required to produce those results and the delay through those gates have made such an adder in practice no faster than other fast adders. Consequently, it is still true that an arrangement is needed which operates rapidly yet does not utilize the very large amount of circuitry required by the prior art.